package com.wrial.sort;
/*
 * @Author  Wrial
 * @Date Created in 10:32 2020/4/15
 * @Description 快排
 */

public class QuickSort {

    public static void quickSort(int[] arr, int left, int right) {
        int pivot = arr[(left + right) / 2];
        int l = left, r = right;
        while (l < r) {
            while (arr[l] < pivot) {
                l++;
            }
            while (arr[r] > pivot) {
                r--;
            }
            if (l > r) break;
            swap(arr, l, r);
            if (arr[l] == pivot) l++;
            if (arr[r] == pivot) r--;
        }
        if (l < right) quickSort(arr, l, right);
        if (r > left) quickSort(arr, left, r);
    }

    private static void swap(int[] arr, int l, int r) {
        int temp = arr[l];
        arr[l] = arr[r];
        arr[r] = temp;
    }

    public static void main(String[] args) {
        int[] arr = new int[]{6, -5, 4, 8, 1};
        quickSort(arr, 0, arr.length - 1);
        for (int i : arr) {
            System.out.println(i);
        }
    }

}
